package com.lwx.leetcode.dp;

import java.util.Arrays;

public class OfferTwo119 {
    public static void main(String[] args) {
        int[] nums = {1,2,0,1};
        OfferTwo119 o = new OfferTwo119();
        int max = o.longestConsecutive(nums);
        System.out.println(max);
    }

    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        //1.将数组排序
        Arrays.sort(nums);
        //2.动态规划  dp[i]以nums[i]结尾的最长连续数组的长度
        int[] dp = new int[nums.length];
        int max = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                dp[i] = Math.max(dp[i], dp[i - 1] + 1);
            }
            max = Math.max(dp[i], max);
        }

        return max;
    }
}
